package gold.digger;

import gold.utils.InputUtil;
import javafx.util.Pair;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1466 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int minReorder(int n, int[][] connections) {
            Map<Integer, List<Pair<Integer, Integer>>> nodeMap = new HashMap<>();
            for (int[] connection : connections) {
                if (!nodeMap.containsKey(connection[0])) nodeMap.put(connection[0], new ArrayList<>());
                if (!nodeMap.containsKey(connection[1])) nodeMap.put(connection[1], new ArrayList<>());
                nodeMap.get(connection[0]).add(new Pair<>(connection[1], 1));
                nodeMap.get(connection[1]).add(new Pair<>(connection[0], -1));
            }

            int cnt = 0, curNode = 0;
            boolean[] visited = new boolean[n];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(0);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    curNode = queue.poll();
                    visited[curNode] = true;

                    for (Pair<Integer, Integer> nextNodePair : nodeMap.get(curNode)) {
                        if (!visited[nextNodePair.getKey()]) {
                            if (nextNodePair.getValue() == 1) cnt++;
                            queue.offer(nextNodePair.getKey());
                        }
                    }
                }
            }

            return cnt;
        }
    }

    public void run() {
        System.out.println(new Solution().minReorder(6, InputUtil.toDoubleIntegerArray("[[0,1],[1,3],[2,3],[4,0],[4,5]]")));
        System.out.println(new Solution().minReorder(5, InputUtil.toDoubleIntegerArray("[[1,0],[1,2],[3,2],[3,4]]")));
        System.out.println(new Solution().minReorder(3, InputUtil.toDoubleIntegerArray("[[1,0],[2,0]]")));
    }

    public static void main(String[] args) throws Exception {
        LC1466 an = new LC1466();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
